package codeRandomThoughts.SortAlgorithm;

import java.util.Arrays;

public class QuickSort {
    /**
     * 快速排序的递归写法
     *
     * @param nums  要排序的数组
     * @param start 起始位置
     * @param end   终止位置(不包含end)
     */
    public static void quickSort(int[] nums, int start, int end) {
        //只有一个元素时不用排序
        if (end - start <= 1) return;
        int pivot = nums[end - 1];
        int i = start;//慢指针
        int j = start;//快指针

        for (j = start; j < end; j++) {
            //j指针寻找比基准点小的元素,如果找到就与i指向的元素进行交换
            if (nums[j] < pivot) {
                int tem = nums[i];
                nums[i] = nums[j];
                nums[j] = tem;
                i++;
            }
        }

        //基准点与i交换
        nums[end - 1] = nums[i];
        nums[i] = pivot;

        //递归排序由基准点划分的左右两瓣序列
        quickSort(nums, start, i);
        quickSort(nums, i + 1, end);
    }

    public static void main(String[] args) {
        int[] nums = {3, 6, 4, 2, 8, 8, 9};
        quickSort(nums, 0, nums.length);
        System.out.println(Arrays.toString(nums));
    }
}
